package leecode;

/**
 * @author csp 2021-04-23
 */
public class Question10 {
    public static void main(String[] args) {
        Question10 question10 = new Question10();
        final boolean match = question10.isMatch("mississippi", "mis*is*ip*.");
        System.out.println(match);
    }

    // 动态规划
    // 状态定义、状态转移
    /*
        1.s[i]=p[j]
        2.p[j]=.
        3.s[i]=p[j-1],p[j]=*
        4.p[j-1]=.,p[j]=*
     */
    public boolean isMatch(String s, String p) {
        int ls = s.length();
        int lp = p.length();
        boolean[][] dp = new boolean[ls + 1][lp + 1];
        // 默认值
        dp[0][0] = true;
        for (int i = 2; i <= lp; i++) {
            dp[0][i] = p.charAt(i - 1) == '*' && dp[0][i - 2];
        }
        for (int i = 1; i <= ls; i++) {
            for (int j = 1; j <= lp; j++) {
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    if (j > 1 && s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.') {
                        dp[i][j] = dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i][j - 2];
                    }
                }
            }

        }
        return dp[ls][lp];
    }

//    public boolean isMatch(String s, String p) {
//        int k = 0;
//        for (int i = 0; i < s.length(); i++) {
//            int re = re(s, i); //当前索引位置
//            if (k > p.length() - 1) {
//                return false;
//            }
//            char a = p.charAt(k);
//            char b = '0';
//            if (k + 1 <= p.length() - 1) {
//                b = p.charAt(k + 1);
//            }
//            if (b == '*') {
//                if (a == '.') {
//                    return true;
//                } else {
//                    if (a == s.charAt(i)) {
//                        i = re;
//                    }else {
//                        i--;
//                    }
//                }
//                k += 2;
//            } else {
//                if (a == '.' || a == s.charAt(i)) {
//                    k += 1;
//                } else {
//                    return false;
//                }
//            }
//        }
//        return true;
//    }
    // 快速排序
    private int re(String s, int index) {
        final char c = s.charAt(index);
        for (int i = index; i < s.length(); i++) {
            if (c != s.charAt(i)) {
                return i - 1;
            }
        }
        return s.length()-1;
    }
}
